\renewcommand{\arraystretch}{1.3}

\section{Mediciones}
\label{sec:mediciones}
Para realizar las mediciones utilizamos las herramientas provistas por la c'atedra para la medici'on de ciclos de \textit{clock}, utilizando una computadora con procesador Intel T2500 2.0GHz Core Duo. El objetivo ser'a medir los distintos algoritmos, comparando las distintas versiones para distintos tipos de imagenes de entrada. Para ello creamos un conjunto de \textit{scripts} de \textit{bash} que realizan las distintas mediciones que necesitamos. Los mismos se encuentran en la carpeta mediciones junto con una explicaci'on de como utilizarlo.

\subsection{Estableciendo Criterios}

Antes de comenzar tuvimos que tomar ciertas decisiones de c'omo ibamos a realizar dichas mediciones. El primer problema que encontramos al utilizar el reloj del procesador para medir es que nuestro proceso puede llegar a ser interrumpido por otros procesos o por el sistema operativo. Hemos tomado dos medidas al respecto, la primera es ejecutar las mediciones estableciendo m'axima la priodidad del proceso. Para ello Linux provee el comando \texttt{nice}, que ejecut'andolo como \textit{root}, permite decirle al sistema operativo que nuestras mediciones tienen prioridad sobre los otros programas en ejecuci'on. 
Mientras que la segunda medida fue realizar mil mediciones por cada prueba, promediando el resultado. El n'umero elegido aparece como una soluci'on de compromiso con el tiempo de ejecuci'on de las muestras.

Otro factor a analizar fue que muestras seleccionamos para medir. Debido a la naturaleza de los algoritmos implementados, podemos ver facilmente que la complejidad esta relacionada directamente con el tama'no de la entrada. Es decir que las dos implementaciones de cada filtro se van a comportar diferente dependiendo del tama'no de la im'agen\footnote{Es importante aclarar que consideramos como tama'no de la imagen, la cantidad total de p'ixeles que esta tiene} y no del tipo de imagen a procesar. Por lo tanto podriamos tomar imagenes de distinto tama'no y comparar como se comportan los distintos filtros y las distintas implementaciones, observando las variaciones de \textit{clocks} con respecto a la cantidad de p'ixeles procesados. Sin embargo elegimos otro camino. Decidimos utilizar un tama'no fijo (dentro de los posibles) de p'ixeles y analizar el comportamiento de los algoritmos al variar la relaci'on entre la cantidad de filas y de columnas de la imagen. 

Para las mediciones base utilizamos una imagen de 800x600. Es decir que estamos trabajando con im'agenes de 480.000 p'ixeles (aprox. 0,5Mp). Luego tomamos distintas im'agenes reacomodando las filas y columnas, seg'un criterios que explicaremos en la siguiente secci'on. Sin embargo a veces no fue posible llegar a la misma cantidad exacta de p'ixeles. En estos casos elegimos combinaciones donde la diferencia sea m'inima y podemos asegurar que en ning'un caso la diferencia de tama'no supera un $0,1\%$ del total.

\subsection{An'alisis de factores}
Antes de decidir las combinaciones de filas y columnas, analizamos con que tipo de im'agenes nuestros algoritmos pod'ian
llegar a comportarse una una manera especial. Como conjetura inicial establecimos que no deberia haber 
fluctuaciones en el las funciones desarrolladas en \C \ ya que el recorrido de la matriz es lineal y
de a un elemento por vez, con lo cual las dimensiones no deber'ian ser un factor relevante. 

En cambio, para el caso de las funciones en \ass, podemos observar que su gran ventaja es que pueden procesar de a muchos datos. Sin embargo su desventaja es que si la imagen no es m'ultiplo de la cantidad de p'ixeles que procesa por iteracion, entonces se debe realizar un reajuste (ver secci'on \ref{sec:algoritmos}), con el objetivo de procesar los 'ultimos p'ixeles de la fila.

Entonces, para elegir exactamente las combinaciones de filas/columnas tenemos que diferenciar dos tipos de
filtros: Los que toman como par'ametro de entrada im'agenes a color (monocromatizar, separar canales) y los que toman im'agenes en blanco y negro
(umbralizar, invertir, normalizar, suavizar).

Para los que toman imagen blanco y negro, los algoritmos procesan de a 16 p'ixeles por vez, con lo cual si el ancho es multiplo de 16, el algoritmo realizar'ia una cantidad justa de lecturas en memoria (\textit{caso favorable}). Por el contrario, cuando la anchura no es multiplo de 5 el algoritmo debe realizar una lectura extra al final de cada fila para procesar los bytes restantes(\textit{caso desfavorable}). Es posible que esta lectura extra se haga solo para procesar un p'ixel. Es decir que estariamos recalculando 15 bytes para procesar solo uno. Esta penalizaci'on se ver'ia acrecentada conforme aumenta la cantidad de filas.

En cambio, los algoritmos que procesan im'agenes a color avanzan de a cinco p'ixeles. Por lo que podemos aplicar el mismo razonamiento que para los algoritmos en blanco y negro modificando el factor de multiplicidad a 5.

Cabe destacar que el filtro suavizar debido a su naturaleza procesa de a 15 p'ixeles, por lo que el caso favorable se calcula como un m'ultiplo de 15 sum'andole dos p'ixeles m'as correspondiente a los bordes que no se procesan.

\subsection{Eleccion de im'agenes}
Como primera medida, realizamos mediciones con una im'agen de 800x600, para poder establecer un punto de comparaci'on para las otras im'agenes de entrada. Luego, teniendo en cuenta lo descripto en la secci'on anterior, elegimos tama'nos de im'agenes que provoquen casos favorables y casos desfavorables, para poder compararlos. 

Para el segundo grupo de mediciones elegimos para los algoritmos en blanco y negro im'agenes de 16 y 17 p'ixeles de ancho para los casos favorable y desfavorable respectivamente. Estos valores son los anchos m'as peque'nos que producen los casos que buscamos. Por el contrario, para los algoritmos a color elegimos anchos de 10 y 11 p'ixeles. Para el filtro suavizar elegimos los anchos 17 y 18 p'ixeles. Es de esperar que en este conjunto de mediciones la penalizaci'on del \ass \ se vea exagerada.

Luego realizamos otro conjunto de mediciones con imagenes mas anchas. Intentando, a priori, diluir las penalizaciones cuando las haya. En este punto encontramos un imprevisto. La librer'ia openCV genera un error al intentar abrir im'agenes mas anchas que 1453 p'ixeles. Es por eso que elegimos un ancho lo mas cercano a ese valor y que fuera m'ultiplo de 16 y de 5, de esta manera nos servir'ia como caso favorable tanto para los algoritmos a color como los de blanco y negro. El ancho elegido fue 1440, ya que cumple las condiciones anteriores. Por otra parte elegimos como ancho para los casos desfavorables el valor 1441. Para el filtro suavizar elegimos los anchos 1442 y 1443 p'ixeles.

\subsection{Experimentos}
\subsubsection{Caso base}
En este experimento se miden todos los filtros en ambas implementaciones en una imagen de 800x600 p'ixeles. En el cuadro \ref{tab:base} podemos observar los siguientes 'indices:

\begin{itemize}
 \item \textbf{ciclos}: ciclos de reloj consumidos por cada implementaci'on.
 \item \textbf{diferencia de ciclos}: modulo de la diferencia entre ciclos de reloj en \C \ y en \ass.
 \item \textbf{porcentaje de mejora}: porcentaje de eficiencia de un implementaci'on con respecto a la otra.
\end{itemize}

En el cuadro podemos ver que en todos los filtros la implementaci'on en \ass \ consume
menos ciclos de reloj, un resultado  que esta dentro de lo esperado, sin embargo llama la atenci'on
lo significativa que es esta diferencia. Por ejemplo en el filtro invertir, que es el que menos instrucciones
realiza, obtuvimos un porcentaje de mejora superior al 96$\%$. El caso del filtro que menos porcentaje
de mejora tuvo fue monocromatizar\_uno, que no obstante, obtuvo una mejora superior al 50$\%$. Si bien
suponiamos que podia haber una diferencia en la eficiencia no sabiamos que seria tan marcada, lo cual es muy 
positivo, ya que significa que dio r'editos implementar en un lenguaje de m'as bajo nivel y mayor dificultad
 a cambio de un mejor rendimiento, siempre utilizando la tecnolog'ia \textit{SSE}.
 
\begin{table}[h!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}
\hline
\sc{funci'on} & \sc{\# pixels }& \sc{ciclos C }& \sc{ciclos ASM }& \sc{$\Delta$ ciclos }& \sc{\% mejora}\\ \hline
invertir & 800x600 & 7.317.170 & 287.367 & 7.029.803 & 96,07\%\\ 
normalizar & 800x600 & 23.331.351 & 1.539.564 & 21.791.786 & 93,40\%\\ 
umbralizar & 800x600 & 13.538.943 & 540.008 & 12.998.935 & 96,01\%\\ 
suavizar & 800x600 & 32.483.342 & 3.968.673 & 28.514.669 & 87,78\%\\ 
monocromatizar\_uno & 800x600 & 17.332.554 & 5.513.335 & 11.819.219 & 68,19\%\\ 
monocromatizar\_inf & 800x600 & 18.555.484 & 4.468.378 & 14.087.106 & 75,92\%\\ 
separar\_canales & 800x600 & 20.421.239 & 6.219.616 & 14.201.623 & 69,54\%\\ 
\hline
\end{tabular}
\caption{Resultados caso base}
\label{tab:base}
\end{center}
\end{table}

\subsubsection{Imagenes altas}
En este experimento comparamos todos los filtros para im'agenes mas altas que anchas. Utilizando medidas especiales para cada caso, como explicamos anteriormente. 

En este experimento introdujimos un nuevo 'indice denominado \textbf{penalizaci'on}. El mismo compara la implementaci'on en \ass, para un \textit{input} favorable y un desfavorable. B'asicamente se calcula como la diferencia de ciclos de esto dos casos expresada en porcentaje, tomando como base la cantidad de ciclos del caso favorable.

En el cuadro \ref{tab:base} podemos observar los resultados para los filtros que toman im'agenes en escala de grises. En ella podemos ver una 
gran mejora de \ass \ con respecto a \C \  tanto en la imagen de 16x30000 como en la de 17x28234. Con esto concluimos que a'un
en un caso no favorable este sigue siendo m'as eficiente. Sin embargo, podemos ver tambien que en los casos no favorables, la implementaci'on en \ass \ demora mucho mas que en los favorables. 

Es notable tambi'en el monstruoso porcentaje de penalizaci'on (340\%, 165\% y
234\%, para invertir, normalizar y umbralizar respectivamente), confirmando nuestras conjeturas sobre los casos favorables y desfavorables. Puntualmente esperabamos una penalizaci'on de alrededor del doble, pero en la mayor'ia de casos fue m'as. Creemos que se debe, de alguna manera, a la complejidad del filtro, es decir a la cantidad de ciclos que toma el procesamiento de una iteraci'on. Por ejemplo, invertir que es por lejos la funcion mas simple de todas, el incremento es de casi tres veces y media, mientras que en normalizar, donde recorremos dos veces la imagen, tenemos un porcentaje mas bajo pero igualmente superior al doble. 

El porcentaje de penalizaci'on para el filtro suavizar tambi'en nos result'o llamativo. Primero porque fue el 'unico que dio exactamente lo que esperamos. pero tambi'en porque dicho porcentaje es bajo en comparaci'on a los otros filtros. Lo cual nos hace inferir que tal vez podriamos implementarlo un poco mas eficientemente, o que tal vez se debe a la complejidad misma del algoritmo. 

En este punto hemos realizado una revisi'on de la implementaci'on del c'odigo de suavizar y vimos que tambien seria posible desarrollar una version que procese de a menos bytes, de esta manera disminuiriamos en un tercio los accesos a memoria\footnote{esto es porque actualmente se leen 18 bytes por iteraci'on - tres lecturas corridas de a un byte}. Ser'ia interesante ver si realmente procesar de menos p'ixeles pero con menos accesos a memoria presenta una mejora en la \textit{performance}. Es una pena que hemos tenido el tiempo suficiente para realizar dicha comprobaci'on. Sin embargo queda como un trabajo a futuro.

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\sc{funci'on} & \sc{\# pixels} & \sc{ciclos C }& \sc{ciclos ASM }& \sc{$\Delta$ ciclos }& \sc{\% mejora }& \sc{penalizaci'on}\\ \hline
invertir & 16x30000 & 7.706.474 & 408.430 & 7.298.044 & 94,70\% & \\ 
 & 17x28234 & 7.642.414 & 1.799.789 & 5.842.625 & 76,45\% & 340,66\%\\ \hline
normalizar & 16x30000 & 24.321.128 & 1.821.235 & 22.499.894 & 92,51\% & \\ 
 & 17x28234 & 23.895.976 & 4.829.856 & 19.066.120 & 79,79\% & 165,20\%\\ \hline
umbralizar & 16x30000 & 14.287.793 & 680.832 & 13.606.961 & 95,23\% & \\ 
 & 17x28234 & 14.253.437 & 2.275.706 & 11.977.731 & 84,03\% & 234,25\%\\ \hline
suavizar & 17x28234 & 29.283.006 & 3.773.630 & 25.509.376 & 87,11\% & \\ 
 & 18x26666 & 29.320.184 & 7.404.941 & 21.915.243 & 74,74\% & 96,23\%\\ 
\hline
\end{tabular}
\caption{Resultados Im'agenes altas blanco y negro}
\label{tab:abyn}
\end{center}
\end{table}

Por otra parte el cuadro \ref{tab:acolor} muestra los resultados para los filtros que toman im'agenes a color. Aqui tambi'en podemos apreciar la gran diferencia de ciclos en \C \ y \ass \ con su porcentaje de mejora en todos los casos mayor que un 50\%. Sin embargo la penalizaci'on para los casos desfavorables no son tan grandes (entre 17\% y 32\%). Creemos que esto se debe a que no estamos en la misma situaci'on de caso favorable/desfavorable de las im'agenes en escala de grises. Para estarlo deberiamos haber procesado ima'agenes de 5 y 6 p'ixeles respectivamente. De esta manera, la primera imagen necesitar'ia solo un ciclo para procesar la fila y y el caso desfavorable necesitaria dos. Aqui el caso favorable necesita dos iteraciones, mientras que el desfavorable necesita 3. Esta diferencia expresada en porcentaje es menor. Cabe aclarar que no elegimos las imagenes reci'en descriptas pues nuestro algoritmo procesa imagenes color de como m'inimo 6 p'ixeles de ancho. 

Como una observaci'on general de estas mediciones de im'agenes altas, en contraste con el caso base podemos apreciar c'omo la distribuci'on de p'ixeles no influencia significativamente en la cantidad de ciclos de reloj de las implementaciones en \C \ mientras que en \ass \ este factor puede llegar tener mucha relevancia. 

\begin{table}[ht!]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\sc{\footnotesize funci'on} & \sc{\footnotesize\# pixels} & \sc{\footnotesize ciclos C }& \sc{\footnotesize ciclos ASM }& \sc{\footnotesize$\Delta$ ciclos }& \sc{\footnotesize\% mejora }& \sc{\footnotesize penalizaci'on}\\ \hline
mono\_uno& 10x48000 & 18.232.058 & 6.168.852 & 12.063.205 & 66,16\% & \\ 
 & 11x43636 & 18.059.469 & 8.144.680 & 9.914.789 & 54,90\% & 32,03\%\\ \hline
mono\_inf & 10x48000 & 18.978.920 & 5.410.115 & 13.568.806 & 71,49\% & \\ 
 & 11x43636 & 18.967.671 & 6.368.449 & 12.599.222 & 66,42\% & 17,71\%\\ \hline
separar\_c & 10x48000 & 20.874.906 & 7.176.690 & 13.698.216 & 65,62\% & \\ 
 & 11x43636 & 20.800.016 & 9.195.779 & 11.604.237 & 55,79\% & 28,13\%\\ \hline
\end{tabular}
\caption{Resultados Im'agenes altas color}
\label{tab:acolor}
\end{center}
\end{table}

\subsubsection{Imagenes anchas}
En este experimento comparamos todos los filtros para im'agenes mas anchas que altas, utilizando las medidas explicadas al inicio de esta secci'on.

La tabla \ref{tab:anchas} nos muestra los resultados de este experimento. Primero podemos observar que el porcentaje de mejora entre las implentaciones es
casi tan alto como el de el caso base en todos los filtros. Sin embargo en este experimento las penalizaciones sufridas por el \ass \ al procesar casos desfavorables no son tan grandes como en el experimento anterior. Esto vuelve a confirmar nuestras conjeturas sobre los casos favorables/desfavorables. 

Que la penalizaci'on sea menor que en el experimento anterior muestra que efectivamente a im'agenes mas anchas el costo de tener que reprocesar algunos pocos p'ixeles se diluye. Podemos pensar al costo de reprocesamiento total como la cantidad de filas por el costo de una iteraci'on. Con las im'agenes altas, las matrices tenian muchas m'as filas con lo cual el costo era alto. Aqui, para la misma cantidad de p'ixeles totales, al tener menos filas, tenemos un costo menor.

Tambi'en es interesante notar c'omo en los filtros que procesan blanco y negro(excepto suavizar) la penalizaci'on todavia es considerable, mientras que en los otros la diferencia es casi imperceptible. Creemos que esto se debe a que en los filtros a color, como cada p'ixel son en realidad tres bytes, la penalizaci'on se diluye mucho mas, pues la informaci'on que se esta procesando es tres veces mas grande que en los casos blanco y negro. Asi que es de esperar la diferencia fuera como m'inimo una tercera parte. 

Sin embargo, no todo es color de rosa en la vida, y nos preguntamos porqu'e suavizar se parece mas a las funciones color que a las de su clase. Nuevamente creemos que tal vez se deba ya sea a la complejidad de la implentaci'on que realizamos(que tiene muchos accesos a memoria) o a la complejidad propia del algoritmo. Tambien es cierto que suavizar no fue el filtro que peor mejora tuvo en el caso base con respecto a la implementaci'on en \C. Y aunque no podamos justificar totalmente el porqu'e, las evidencias muestran que este filtro es el mas estable de todos, pues a pesar de las variaciones que estamos realizando los resultados no cambian tanto como en los otros filtros y son siempre similares al caso base.

Otra observaci'on general que notamos fue que aqui tambi'en la cantidad de ciclos consumidos por la implementaci'on en \C \ es
similar al de los casos base, por el contrario la implementaci'on en \ass \ en todos los casos los filtros consumen m'as ciclos que en su caso base (salvo normalizar que la cantidad de ciclos es comparable).

\begin{table}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
\sc{\footnotesize funci'on} & \sc{\footnotesize\# pixels} & \sc{\footnotesize ciclos C }& \sc{\footnotesize ciclos ASM }& \sc{\footnotesize$\Delta$ ciclos }& \sc{\footnotesize\% mejora }& \sc{\footnotesize penalizaci'on}\\ \hline
invertir & 1440x333 & 7.277.945 & 313.567 & 6.964.378 & 95,69\% &  \\ 
  & 1441x333 & 7.274.547 & 459.617 & 6.814.930 & 93,68\% & 46,58\%\\ \hline
normalizar & 1440x333 & 23.352.742 & 1.557.537 & 21.795.205 & 93,33\% &  \\ 
  & 1441x333 & 23.326.450 & 1.793.687 & 21.532.763 & 92,31\% & 15,16\%\\ \hline
umbralizar & 1440x333 & 13.004.767 & 543.850 & 12.460.917 & 95,82\% &  \\ 
  & 1441x333 & 13.013.609 & 715.497 & 12.298.113 & 94,50\% & 31,56\%\\ \hline
suavizar & 1442x333 & 32.468.271 & 3.905.847 & 28.562.424 & 87,97\% &  \\ 
  & 1443x333 & 32.483.078 & 3.945.091 & 28.537.988 & 87,85\% & 1,00\%\\ \hline
mono\_uno & 1440x333 & 17.292.896 & 5.499.913 & 11.792.983 & 68,20\% &  \\ 
  & 1441x333 & 17.337.919 & 5.529.326 & 11.808.594 & 68,11\% & 0,53\%\\ \hline
mono\_inf & 1440x333 & 18.526.267 & 4.450.636 & 14.075.631 & 75,98\% &  \\ 
  & 1441x333 & 18.521.016 & 4.483.062 & 14.037.954 & 75,79\% & 0,73\%\\ \hline
separar\_c& 1440x333 & 20.427.885 & 6.163.018 & 14.264.867 & 69,83\% &  \\ 
  & 1441x333 & 20.457.241 & 6.214.148 & 14.243.092 & 69,62\% & 0,83\%\\ \hline
\end{tabular}
\caption{Resultados Im'agenes anchas}
\label{tab:anchas}
\end{center}
\end{table}

